抽象类型

  在将 Stack 从用一个模块实现的“假类型”转变为一个真正的类型的过程中，有一个性质被丢掉了：表示方式没有与用户界面分离，反而变成了使用 Stack 的程序片段里将要包含的一个部分。这个表示完全是私用的，因此只能通过成员函数访问，然而它却出现在那里。如果这个表示有了某种显著变化，那些使用它的代码就必须重新编译。这是为做出在行为方式上完全像内部类型的具体类型时所付出的一个代价。特别因为在不知道一个类型表示的大小情况下，我们就无法获得这个类型的真正的局部变量。

  在类型不常改变，而且局部变量又确实提供了我们极需要的清晰性和效率的那些地方，这种方式是完全可以接受的，也是很理想的。但是，如果我们需要将堆栈的用户与堆栈表示的修改完全隔离开，前面的这个Stack就不够好了。针对这个问题的解决方案能得到界面与表示的完全分离，这时需要放弃的就是真正的局部变量。

我们首先定义界面：

    class Stack
    {
    public:
        class Underflow{};    // 用于异常
        class Overflow{};     // 用于异常

        virtual void push(char c) = 0;
        virtual char pop() = 0;
    };

词语 virtual 在 Simula 和 C++ 里的意思是“可以在今后由这个类所派生的类里重新定义”。由 Stack 派生出的一个类将提供这个 Stack 界面的一个具体实现。有些古怪 =0 语法形式说明在由 Stack 派生的某些类中必须定义这些函数。这样，这个 Stack 就能作出任何实现 push() 和 pop() 的类的界面了。

该 Stack 以如下方式使用：

    void f(Stack& s_ref)
    {
        s_ref.push('c');
        if(s_ref.pop() != 'c') throw Bad_pop();
    }

请注意 f() 如何使用着Stack界面，而完全忽略了实现的细节。为另外一些不同的类提供界面的类也常常被称做多态类型。

  毫不奇怪，有关实现的所有东西都可以与前面那个具体 Stack 类完全一样，我们就是从那里提取出了界面 Stack：

    class Array_stack : public Stack {
        char* p;
        int max_size;
        int top;
    public:
        Array_stack(int s);
        ~Array_stack();

        void push(char c);
        char pop();
    };

开始处的 “:public” 可以读作“由其派生”，“实现”或者“是它的子类型”。

对于像 f() 这样的使用着 Stack，但却完全不管其实现细节的函数，需要有另外的函数去为它创建对象，使 f() 一类的函数可以在这些对象上操作。例如，

    void g()
    {
        Array_stack as(200);
        f(as);
    }

因为 f() 根本不知道 Array_stack，只知道 Stack 界面，它在 Stack 的另一个不同实现上工作起来也同样好。例如，

    class List_stack : public Stack {    // List_stack 实现Stack
        list<char> lc;                   // （标准库）字符的表
    public:
        List_stack() { }
        void push(char c) { lc.push_front(c); }
        char pop();
    };

    char List_stack::pop()
    {
        char x = lc.front();    // 取得第一个元素
        lc.pop_front();         // 删除第一个元素
        return x;
    }

在这里，具体表示采用了一个字符的表。lc.push_front(c) 将 c 添加为 lc 的第一个字符，调用 lc.pop_front() 删除第一个字符，而 lc.front() 表示 lc 的第一个字符。

下面函数建立起一个 List_stack，并让 f() 去使用它：

    void h()
    {
        List_stack ls;
        f(ls);
    }

代码（edit by shenjun）:

    #include <list>

    class Stack
    {
    public:
        /*class Underflow{};
        class Overflow{};*/

        virtual void push(char c) = 0;     // 纯虚（抽象）函数
        virtual char pop() = 0;            // 纯虚（抽象）函数
        virtual void show() = 0;           // 纯虚（抽象）函数
    };

    class Bad_pop{ /* 实现 用做异常 */ };
    class Bad_push { /* 实现 用做异常 */ };
    //class Underflow{ /* 实现 用做异常 */ };
    //class Overflow{ /* 实现 用做异常 */ };

    void f(Stack& s_ref)
    {
        /*s_ref.push('c');
        if (s_ref.pop() != 'c') throw Bad_pop();*/

        //char name[] {"shenjun"};        // C风格字符串初始化
        char name[] = "shenjun";
        for (char* p = name; *p != 0; p++)
        {
            s_ref.push(*p);
        }
        s_ref.show();

        /*for (size_t i = 0; i < 7; i++)
        {
            printf("%c", s_ref.pop());
        }
        printf("\n");*/
    }

    class Array_stack : public Stack {

        char* p;
        int max_size;
        int top;

    public:
        Array_stack(int s);
        ~Array_stack();

        void push(char c);
        char pop();
        void show();
    };

    Array_stack::Array_stack(int s)
    {
        max_size = s;
        p = new char[s];
        top = 0;
        p[0] = 0;
    }

    Array_stack::~Array_stack()
    {
        top = 0;
        delete [] p;
    }

    void Array_stack::push(char c)
    {
        if (top == max_size) throw Bad_push();

        p[top] = c;
        ++top;
        p[top] = 0;
    }

    char Array_stack::pop()
    {
        if (top == 0) throw Bad_pop();

        --top;
        char c = p[top];
        p[top] = 0;
        return c;
    }

    void Array_stack::show()
    {
        for (size_t i = 0; i < top; i++)
        {
            printf("%c", p[i]);
        }
        printf("\n");
    }

    void g()
    {
        Array_stack as(200);
        f(as);
    }

    class List_stack : public Stack {
        std::list<char> lc;                           // #include <list>

    public:
        List_stack(){}
        void push(char c) { lc.push_back(c); }        // lc.push_begin(c);
        char pop();
        void show();
    };

    char List_stack::pop()
    {
        char x = lc.front();           // 取得第一个元素
        lc.pop_front();                // 删除第一个元素
        return x;
    }

    void List_stack::show()
    {
        //typedef std::list<char>::iterator it;
        typedef std::list<char>::const_iterator it;
        for (it i = lc.begin(); i != lc.end(); i++)
        {
            printf("%c", *i);
        }
        printf("\n");
    }

    void h()
    {
        List_stack ls;
        f(ls);
    }

🔚